1824D - LuoTianyi and the Function - CodeForces Solution

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int l[N],r[N],z[N],tot,n,ans[N],a[N],q,tj[N],x,y,dx,dy;
struct ss{
	int t1[N],t2[N];
	int lw(int x){return x&(-x);}
	void add(int x,int k){int dq=x; for(;x<=n;x+=lw(x)) t1[x]+=k*(1-dq),t2[x]+=k;}
	void jr(int l,int r,int k){add(l,k),add(r+1,-k);}
	int qry(int x){
		int res=0,dq=x;
		for(;x;x-=lw(x)) res+=t1[x]+t2[x]*dq;
		return res;
	}
	int xw(int l,int r){return qry(r)-qry(l-1);}
}T,T1;
struct ss1{int l,r,opt,id;};vector<ss1> v[N];
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=q;i++) cin>>x>>dx>>y>>dy,v[x].push_back({y,dy,1,i}),v[dx+1].push_back({y,dy,-1,i});
	for(int i=n;i>=1;i--){
		int dq;
		if(!tj[a[i]]) dq=n; else dq=tj[a[i]]-1;
		tj[a[i]]=i;
		while(tot&&r[tot]<=dq) T.jr(l[tot],r[tot],-(i-z[tot])*(n-i)),T1.jr(l[tot],r[tot],i-z[tot]),tot--;
		if(tot&&l[tot]<=dq) T.jr(l[tot],dq,-(i-z[tot])*(n-i)),T1.jr(l[tot],dq,i-z[tot]),l[tot]=dq+1;
		l[++tot]=i,r[tot]=dq,z[tot]=i,T.jr(i,i,-i*(n-i)),T1.jr(i,i,i);
		for(auto d1:v[i]) ans[d1.id]+=(T1.xw(d1.l,d1.r)*(n-i+1)+T.xw(d1.l,d1.r))*d1.opt;
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<endl;
	return 0;
}